// https://www.lintcode.com/problem/tower-of-hanoi/my-submissions

class Solution {
public:
    /**
     * @param n: the number of disks
     * @return: the order of moves
     */
     
    void help(int n, string start, string mid, string end, vector<string>& res) {
        if (n < 1) {
            return;
        }
        help(n - 1, start, end, mid, res);
        res.push_back("from " + start + " to " + end);
        help(n - 1, mid, start, end, res);
    }
    vector<string> towerOfHanoi(int n) {
        vector<string> res;
        help(n, "A", "B", "C", res);
        return res;
    }
    
    // vector<string> help(int n, string start, string mid, string end) {
    //     vector<string> res;
    //     if (n == 1) {
    //         res.push_back("from " + start + " to " + end);
    //     }
    //     else if (n == 2) {
    //         res.push_back("from " + start + " to " + mid);
    //         res.push_back("from " + start + " to " + end);
    //         res.push_back("from " + mid + " to " + end);
    //     }
    //     else {
    //         vector<string> tmp1 = help(n - 1, start, end, mid);
    //         vector<string> tmp2 = help(1, start, mid, end);
    //         vector<string> tmp3 = help(n - 1, mid, start, end);
    //         res.insert(res.end(), tmp1.begin(), tmp1.end());
    //         res.insert(res.end(), tmp2.begin(), tmp2.end());
    //         res.insert(res.end(), tmp3.begin(), tmp3.end());
    //     }
        
    //     return res;
    // }
    // vector<string> towerOfHanoi(int n) {
    //     vector<string> res = help(n, "A", "B", "C");
    //     return res;
    // }
};